//
// Created by zx208 on 2024/10/17.
//

// 设有一个带头结点的单链表hc，
// 将hc拆分按照奇偶位置成两个带头结点的单链表ha和hb
// 要求ha利用原hc的头结点，算法的空间复杂度为O（1）

// 思路：利用头插法是逆序 而尾插法是正序

#include "../SingleLinkedList.h"

LinkedList Create_List_R(LinkedList head, int n){

    // 先创建头指针
    head = (LinkedList) malloc(sizeof( LNode));
    head->next = NULL;

    // 创建一个工作指针
    LinkedList node = head;

    for (int i = 0; i < n; ++i) {
        LinkedList p = (LinkedList) malloc(sizeof( LNode));
        int data;
        scanf(" %d", &data);
        p->data = data;
        p->next = node->next; // 即 p->next = NULL;
        node->next = p;
        node = p;
    }
    return head;
}

void PrintLL(LinkedList L){
    LNode *node = L->next;
    while(node){
        printf("%d ", node->data);
        node = node->next;
    }
}

void Split_LL(LinkedList La, LinkedList Lb, LinkedList Lc){
    LinkedList p = Lc->next, q = La, tail = Lb;
    int i = 1;

    while(p){
        if(i % 2){
            q->next = p;
            q = q->next;
        } else{
            tail->next = p;
            tail = tail->next;
        }
        i++;
        p = p->next;
    }
    q->next = NULL;
    tail->next = NULL;
}

int main(void){
    LinkedList La = (LinkedList) malloc(sizeof( LNode)), Lb = (LinkedList) malloc(sizeof( LNode)), Lc= NULL;
    Lc = Create_List_R(Lc, 6);
    Split_LL(La, Lb, Lc);
    PrintLL(La);
    printf("\n\n");
    PrintLL(Lb);
    return 0;
}

// 1 4 2 5 3 6